/*
	解法：用unordered_map放第一个整数和下标，边遍历nums边查找unordered_map，找到后立即返回下标
  
	为什么：因为既要存放值又要存放下标，所以考虑用map类数据结构，unordered_map count(key)查询效率更高
			key: 元素值，value: 元素下标，这样做count(key)时间复杂度为O(1)
			
	时间复杂度：O(n)，空间复杂度：O(n)
 */

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution
{
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		unordered_map<int, int> hashmap;
		
		for (int i = 0; i < (int)nums.size(); i++)
		{
			int complement = target - nums[i];
			
			if (hashmap.count(complement) == 0)
			{
				hashmap[nums[i]] = i;
			}
			else
			{
				return{hashmap[complement], i};
			}
			
		}
		
		return {};  // 按题意一定有解，这里只是语法完整，return {} 理论上永远不会执行
					//C++ 编译器要求函数必须有返回值，所以就加了 return {}; 作为兜底，防止编译器报错
	}
};

/*
	key: 元素下标，value: 元素值
	时间复杂度：O(n²)，空间复杂度：O(n)
  
class Solution
{
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		unordered_map<int, int> hashmap;  // key: 下标, value: 元素值
	
		for (int i = 0; i < nums.size(); i++)
		{
			int complement = target - nums[i];
		
			//这里无法通过 count(complement) 快速查找
			// 需要手动遍历 value 来找是否存在 complement
			for (auto it = hashmap.begin(); it != hashmap.end(); ++it)
			{
				if (it->second == complement)
				{
					return { it->first, i };  // it->first 是下标
				}
			}
		
			// 插入当前值
			hashmap[i] = nums[i];
		}
	
		return {};
	}
};	
 */

int main()
{
	Solution solution;
	
	vector<int> nums = {3, 1, 3, 6};
	int target = 9;
	
	vector<int> result = solution.twoSum(nums, target);
	
	cout << "Indices: [" << result[0] << ", " << result[1] << "]" << endl;
	
	return 0;
}


